// 1019. [优先队列我的结构体]简单负载均衡
// https://oj.rnd.huawei.com/problems/1019/details
// 负载分担规则：按顺序循环分配服务器，如：有3台服务器且都空闲，分配的方式为
// 1->2->3->1… ； 如果某台服务器繁忙，则跳过该服务器；
// 如果一条消息到达时所有服务器繁忙，则丢弃这条消息。
// 输出处理负载最多的服务器编号，注意按升序输出。
// 输入 3
// 7
// 1 15
// 2 10
// 12 10
// 5 10
// 6 10
// 30 15
// 32 10
// 输出 1 3

#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;

struct Message {
  int start;
  int load;
};

struct Serv {
  size_t No;
  int freeStart;  // start include time, 0
  long loadTotal;
  bool operator>(Serv oth) const {  // greater
    return freeStart > oth.freeStart;
  }
};

class Solution {
  static bool cmp(Serv s1, Serv s2) { return s1.freeStart > s2.freeStart; }

  // 注意引用
  void updateServ(vector<Serv>& vtServ, Serv s) { vtServ[s.No - 1] = s; }

 public:
  // 待实现函数，在此函数中填入答题代码;
  vector<size_t> FindHighestLoadServers(size_t serverNum,
                                        const vector<Message>& messages) {
    vector<size_t> result;
    vector<Message> sortedMsg = messages;
    vector<Serv> vtSvr(serverNum);
    for (size_t i = 0; i < vtSvr.size(); i++) {
      vtSvr[i].No = i + 1;
      vtSvr[i].freeStart = 0;
      vtSvr[i].loadTotal = 0;
    }
    std::sort(sortedMsg.begin(), sortedMsg.end(),
              [](Message m1, Message m2) { return m1.start < m2.start; });
    size_t curSvr = 0;
    priority_queue<Serv, vector<Serv>, greater<Serv> > queServer;
    for (size_t i = 0; i < sortedMsg.size(); i++) {
      if (queServer.size() < serverNum) {
        Serv& svr = vtSvr[curSvr];
        svr.freeStart = sortedMsg[i].start + sortedMsg[i].load;
        svr.loadTotal += sortedMsg[i].load;
        updateServ(vtSvr, svr);  // 注意同步
        queServer.push(svr);
        curSvr = (curSvr + 1) % serverNum;
      } else if (queServer.size() == serverNum) {
        Serv svr = queServer.top();
        if (sortedMsg[i].start >= svr.freeStart) {
          queServer.pop();
          svr.freeStart = sortedMsg[i].start + sortedMsg[i].load;
          svr.loadTotal += sortedMsg[i].load;  // 注意累加
          updateServ(vtSvr, svr);              // 注意同步
          queServer.push(svr);
        } else {
          // drop message
        }
      }
    }
    std::sort(vtSvr.begin(), vtSvr.end(), [](Serv s1, Serv s2) {
      if (s1.loadTotal == s2.loadTotal) {
        return s1.No < s2.No;
      }
      return s1.loadTotal > s2.loadTotal;
    });

    result.push_back(vtSvr[0].No);
    for (size_t i = 1; i < vtSvr.size(); i++) {
      if (vtSvr[i].loadTotal == vtSvr[i - 1].loadTotal) {
        result.push_back(vtSvr[i].No);
      } else {
        break;  // 注意跳出
      }
    }
    return result;
  }
};

inline int ReadInt() {
  int number;
  cin >> number;
  return number;
}
template <typename T>
inline void WriteVector(const vector<T>& objects, char delimeter = ' ') {
  auto it = objects.begin();
  if (it == objects.end()) {
    return;
  }
  cout << *it;
  for (++it; it != objects.end(); ++it) {
    cout << delimeter << *it;
  }
  cout << endl;
}

// 10000
// 30000

// 3
// 7

// Message m;
// m.start = 1; m.load = 15; msgs.push_back(m);
// m.start = 2; m.load = 10; msgs.push_back(m);
// m.start = 12; m.load = 10; msgs.push_back(m);
// m.start = 5; m.load = 10; msgs.push_back(m);
// m.start = 6; m.load = 10; msgs.push_back(m);
// m.start = 30; m.load = 15; msgs.push_back(m);
// m.start = 32; m.load = 10; msgs.push_back(m);

int main_1019_2() {
  int serverNum = 3;
  serverNum = ReadInt();
  int n = 7;
  n = ReadInt();
  vector<Message> msgs;
  for (int i = 0; i < n; ++i) {
    Message obj;
    cin >> obj.start >> obj.load;
    msgs.push_back(obj);
  }

  Solution solu;
  vector<size_t> result = solu.FindHighestLoadServers(serverNum, msgs);
  WriteVector(result, ' ');

  return 0;
}
